package leetcode.code1452;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

import leetcode.IDebug;
import leetcode.helper.H;

public class Solution implements IDebug {

	public List<Integer> peopleIndexes(List<List<String>> favoriteCompanies) {
		int size = favoriteCompanies.size();
		Integer[] idxs = new Integer[size];
		for (int i = 0; i < size; i++) {
			idxs[i] = i;
		}
		Arrays.sort(idxs, (a, b) -> {
			return favoriteCompanies.get(b).size() - favoriteCompanies.get(a).size();
		});
		Map<String, List<Integer>> map = new HashMap<>();
		List<Integer> ans = new ArrayList<>();
		for (int i = 0; i < size; i++) {
			int id = idxs[i];
			List<String> fc = favoriteCompanies.get(id);
			Set<Integer> set = new HashSet<>();
			for (int j = 0; j < fc.size(); j++) {
				String f = fc.get(j);
				List<Integer> ids = map.getOrDefault(f, new ArrayList<>());
				if (j == 0) {
					set.addAll(ids);
				} else {
					Set<Integer> cur = new HashSet<>();
					for (int is : ids) {
						if (set.contains(is)) {
							cur.add(is);
						}
					}
					set = cur;
				}
				map.computeIfAbsent(f, key -> new ArrayList<>()).add(id);
			}
			if (set.isEmpty()) {
				ans.add(id);
			}
		}
		Collections.sort(ans);
		return ans;
	}

	@Override
	public void debug4() {
		H.printObjects(this.peopleIndexes(H.str2intlist2("[[\"leetcode\",\"google\",\"facebook\"],[\"google\",\"microsoft\"],[\"google\",\"facebook\"],[\"google\"],[\"amazon\"]]")));;
		H.printObjects(this.peopleIndexes(H.str2intlist2("[[\"leetcode\",\"google\",\"facebook\"],[\"leetcode\",\"amazon\"],[\"facebook\",\"google\"]]")));;
		H.printObjects(this.peopleIndexes(H.str2intlist2("[[\"leetcode\"],[\"google\"],[\"facebook\"],[\"amazon\"]]")));;

	}

	@Override
	public void debug3() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug2() {
		// TODO Auto-generated method stub

	}

	@Override
	public void debug1() {
		// TODO Auto-generated method stub

	}

	public static void main(String[] args) {
		Solution so = new Solution();
		so.debug1();
		so.debug2();
		so.debug3();
		so.debug4();

	}

}

